package com.wrial.kind.tree;
/*
 * @Author  Wrial
 * @Date Created in 20:08 2020/8/16
 * @Description
 * 给定一个二叉树，判断其是否是一个有效的二叉搜索树。
    假设一个二叉搜索树具有如下特征：
    节点的左子树只包含小于当前节点的数。
    节点的右子树只包含大于当前节点的数。
    所有左子树和右子树自身必须也是二叉搜索树。
    示例 1:
    输入:
        2
       / \
      1   3
    输出: true
    输入:
        4
       / \
      1   5
         / \
        3   6
    输出: false
    解释: 输入为: [5,1,4,null,null,3,6]。
         根节点的值为 4 ，但是其右子节点值为 6 。

 *
 */

public class IsValidBST {
    /**
     * 如示例2所示，不能仅仅比较相邻的一个子树，在左子树下面的不能有任何一个比当前根元素小，右边也同理
     * 因此需要一个上界和一个下界来规范
     * 根据左右值限定区间（注意此处递归时必须开始是null，否则会有越界问题，或者使用long）
     * @param root
     * @return
     */

    public boolean isValidBST(TreeNode root) {
        if (root == null) return true;
        return helper(root, null, null);
    }

    private boolean helper(TreeNode root, Integer maxValue, Integer minValue) {
        if (root == null) return true;
        int val = root.val;
        if (maxValue != null && val >= maxValue) return false;
        if (minValue != null && val <= minValue) return false;

        if (!helper(root.left, val, minValue)) return false;
        if (!helper(root.right, maxValue, val)) return false;
        return true;
    }


    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }
}
